//图的广度优先遍历（bfs）
/*
  类似树的层序遍历
*/

#include "LinkQueue.h"
#include "MGraph.h"
#include <iostream>

using namespace std;

bool visited[MaxVertexNum]; //访问数组，用于标记对应顶点是否被访问过

inline void visit(int v) //访问操作
{
    cout << v << ' ';
    return;
}

//从顶点v开始的广搜
void BFS(MGraph G, int v)
{
    LinkQueue Q;  //链队
    InitQueue(Q); //初始化链队

    visit(v);          //访问操作
    visited[v] = true; //访问完后，标记已访问
    EnQueue(Q, v);     //入队

    while (!IsEmpty(Q)) //只要队不空就一直执行
    {
        DeQueue(Q, v);                                                       //把即将处理的顶点出队
        for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) //把所有连接在顶点v上且未被访问的顶点都入队
            if (!visited[w])                                                 //如果该顶点未被访问
            {
                visit(w);          //访问该顶点
                visited[w] = true; //标记已访问
                EnQueue(Q, w);     //入队
            }
    }
    return;
}

int main()
{
    MGraph G;        //以邻接矩阵来实现，可确保bfs遍历序列唯一
    G.DirStatue = 0; //该图为无向图，且不带权
    cout << "input vexnum and arcnum:\n";
    cin >> G.vexnum >> G.arcnum; //确认该图顶点数和边数
    Init(G);                     //初始化图G

    //得到该带权图的邻接矩阵
    cout << "please input (x y):\n";
    for (int x, y, i = 0; i < G.arcnum; ++i)
    {
        cin >> x >> y;
        AddEdge(G, x, y);
    }

    //测试代码，以顶点1开始遍历
    BFS(G, 1);
    return 0;
}